1. Field of the Invention
The present invention relates generally to an error correction decoding apparatus and method. More particularly, the present invention relates to a decoding apparatus and method for improving decoding performance by reducing decoding complexity of a Low Density Parity Check (LDPC) code.
2. Description of the Related Art
In general, a digital communication system suffers from errors due to noise generated in a transmission path and corrects the errors with various algorithms to remove the generated errors. In a wireless communication system employing 3rd Generation Partnership Project (3GPP) or 3rd Generation Partnership Project 2 (3GPP2), which is currently under standardization, the use of convolutional codes and turbo codes is proposed for the transmission of voice and control signals. The turbo code for high-speed transmission is advantageous in that it can obtain a very low bit error rate (BER) at a low signal-to-noise ratio (SNR). However, the turbo code is relatively short in the minimum distance between codewords. As a result, when a signal coded with the turbo code is decoded, an error floor may occur at a desired bit error point, and a detection failure probability for defective codewords during the decoding is relatively high. Recently, therefore, new attention has been given to an LDPC code which is similar or superior to the turbo code in performance.
The LDPC code has greater minimum distance than the turbo code having the same length as that of the LDPC. As a result, the error floor occurs at a very low BER as compared with the turbo code, and the detection failure probability for defective codewords is very low, approximately ‘0’ on an experimental basis. In addition, the LDPC code can be implemented in a parallel structure, contributing to a dramatic reduction in decoding time, and can be subject to efficient decoding stop without a decoding stop algorithm or overhead such as cyclic redundancy check (CRC) bits added through parity check performed every iterative decoding.
FIG. 1 is a diagram illustrating an LDPC structure.
Referring to FIG. 1, the LDPC code is a code having a parity check matrix in which the number of is in each row and column is very small, and its structure can be defined by a factor graph including check nodes 100, variable nodes 110, and edges 115 for connecting the check nodes 100 to the variable nodes 110. A value delivered from the check node 100 to the variable node 110 after check node processing becomes a check node message 115a, and a value delivered from the variable node 110 to the check node 100 after variable node processing becomes a variable node message 115b. 
A decoding process of the LDPC code is achieved by iterative decoding based on a ‘sum-product’ algorithm. The optimal sum-product algorithm includes relatively complex calculations. Another decoding method can be provided based on a suboptimal message-passing algorithm such as a ‘min-sum’ algorithm, which is a simplified sum-product algorithm.
The LDPC code will now be described in greater detail with reference to FIG. 2.
FIG. 2 is a diagram illustrating an exemplary structure of an LDPC code according to a factor graph and a parity check matrix.
Referring to FIG. 2, a factor graph of an LDPC code includes four check nodes 200 representing predetermined parity check equations of the LDPC code, eight variable nodes 210 representing symbols, and edges 220 representing relationships therebetween. The edges 220 connect each check node 200 to the variable node 210 corresponding to a code symbol included in a parity check equation represented by the check node 200. Herein, the number of the variable nodes 210 connected to each of the check nodes 200 is fixed at 6 and the number of the check nodes 200 connected to each of the variable nodes 210 is fixed at 3, thereby illustrating an example of a regular LDPC code. Although not illustrated, an irregular LDPC code can be provided in which the number of edges connected to each of the check nodes 200 and the variable nodes 210 is not fixed.
A parity check matrix (H) 230 corresponding to the factor graph is shown below the factor graph in FIG. 2. This is similar to the graphic expression of the parity check equations. In the parity check matrix 230, the number of 1s in each column and each row is fixed. That is, each column of the parity check matrix 230 has three 1s corresponding to the connections between each of the variable nodes 210 and the check nodes 200, and each row has six 1s corresponding to the connections between each of the check nodes 200 and the variable nodes 210.
A process of decoding the LDPC code is achieved by iterating a process of exchanging messages generated and updated for each individual node by the variable nodes and the check nodes in the factor graph. In this case, each node updates the messages using the sum-product algorithm or a similar suboptimal algorithm. The iterative decoding process of the LDPC code, based on the foregoing process, will now be described herein below.
FIG. 3 is a block diagram of a general LDPC code.
Referring to FIG. 3, an LDPC decoding apparatus includes a memory block 300 for storing received information, a variable node processor 340 for performing variable node-related calculations (hereinafter referred to as “variable node processing”), a check node processor 320 for performing check node-related calculations (hereinafter referred to as “check node processing”), a parity check block 330 for determining whether to perform iterative decoding by checking if all errors were corrected in check nodes, and a memory access controller 310.
A brief description of the LDPC decoding order will now be made herein below.
First, received symbols are stored in the memory block 300 as initial log likelihood ratio (LLR) values of the variable nodes. The LLR values stored in the memory block 300 become variable node output messages to their associated edges.
Second, the check node processor 320 reads variable node values (that is, LLR values which are variable node messages) stored in the memory block 300. The parity check block 330 performs parity check on the read variable node values, and the check node processor 320 calculates a transmission path transition probability as 0 and 1, of the read variable node values and overwrites the calculated probability values (that is, check node messages) back in the memory block 300 as variable node values.
Third, the variable node processor 340 reads the variable node values overwritten in the memory block 300, and calculates variable node messages including final LLR values using the read variable node values.
Fourth, the second and third processes are iterated until the parity check block 330 succeeds in parity check and determines to stop the iterative decoding, thereby increasing reliability.
The variable node processor 340 and the check node processor 320 read and calculate values from memory areas corresponding to positions of 1s in the columns and rows of a parity check matrix, respectively, and overwrite the calculated values back in the same memory areas.
In the second and third processes, the variable node processor 340 and the check node processor 320 each calculate output messages through input values (that is, check node messages and variable node messages) received from the edges connected thereto. Specifically, the check node processor 320 and the variable node processor 340 each calculate values read from sub-metric blocks in the memory block 300, being mapped to positions of 1s in rows and columns of the parity check matrix, and store the calculated values therein.
A process of calculating the variable node messages and the check node messages will now be described in greater detail herein below. Herein, a degree dc represents the number of variable nodes connected to a check node and is equal to the number of 1s existing in each column in the parity check matrix, and a degree dv represents the number of check nodes connected to a variable node and is equal to the number of 1s existing in each row in the parity check matrix.
First, a check node message transmitted from an mth check node to an nth variable node is updated using Equation (1) below.
                              r          mn                =                              tanh                          -              1                                ⁡                      (                                          ∏                                  i                  =                  1                                                                      d                    c                                    -                  1                                            ⁢                                                          ⁢                              tanh                ⁡                                  (                                                            q                      i                                              (                        j                        )                                                              2                                    )                                                      )                                              (        1        )            
That is, Equation (1) represents an equation for jth iterative decoding on a message of the mth check node connected to dc variable nodes, and qi(j) denotes a message generated by reordering a variable node message delivered to the mth check node. When a variable node message delivered from an nth variable node to an mth check node is denoted by qnm(j), the reordering is performed on the basis of q0(j)=qnm(j). A message rmn(j) delivered from the mth check node to the nth variable node is comprised of a non-linear function of input variable node messages, except for q0(j).
Next, a variable node message is updated in accordance with Equation (2) below.
                              q          nm                      (                          j              +              1                        )                          =                              q            nm                          (              0              )                                +                                    ∑                              i                =                1                                                              d                  y                                -                1                                      ⁢                          i                              (                j                )                                                                        (        2        )            
Equation (2) represents an equation for an nth variable node with a degree dv, and the variable node message becomes the sum of an initial LLR value qnm(0) and input check node messages, except for r0(j)=rmn(j) indicative of an input from the mth check node.
Finally, at each iterative decoding, the LLR value is updated using Equation (3) below.
                              L          n                      (                          j              +              1                        )                          =                              L            n            0                    +                                    ∑                              i                =                0                                                              d                  y                                -                1                                      ⁢                          r                              i                                  (                  j                  )                                                                                        (        3        )            
Herein, Ln(j) denotes an LLR value after (j+1)th iterative decoding of an nth variable node, and is updated with the sum of an initial LLR value Ln(0) and input check node messages.
As can be noted from Equation (2) and Equation (3), the variable node message update and the LLR update can be implemented simply with the summation, but the check node message update is expressed in a non-linear function, causing an increase in hardware complexity. Accordingly, there is a need for an optimal algorithm for reducing the hardware complexity.
As described above, a calculation algorithm for separately performing check node processing and variable node processing uses a high-capacity memory. That is, the memory block 300 must store therein information on all of the edges, and the check node processor 320 and the variable node processor 340 each read necessary values from the memory block 300 to perform corresponding calculations and calculate LLR values. In this case, the algorithm performs variable node processing after performing check node processing on all of the edges. As a result, the variable node processor 340 is disabled while the algorithm performs the check node processing. Likewise, while the algorithm performs variable node processing, the check node processor 320 is disabled. That is, the algorithm must read various types of data from the single memory block to perform corresponding processing, causing a memory access delay.
Accordingly, a need exists for a method and apparatus for improving decoding performance by reducing decoding complexity of a Low Density Parity Check (LDPC) code.